package com.platform.modules.alg.alglib.poj2513;

public class Poj2513 {
    private int maxn = 500010;
    private int maxz = 26; // 不同字符个数，小写字母 26
    int trie[][] = new int[maxn][maxz];
    boolean end[];
    int tot; // 字符串数,下标
    int color = 0; //颜色编号指针，最终为颜色总个数
    int degree[];
    int col[]; // 结点的度数，颜色号
    int fa[]; // 祖先，即集合号

    public String output = "";

    void Init() {
        end = new boolean[maxn]; // 标记结束
        degree = new int[maxn];
        col = new int[maxn];
        fa = new int[maxn];
        tot = 1;
    }

    // 找祖先
    int Find(int x) {
        if (fa[x] != x)
            fa[x] = Find(fa[x]);
        return fa[x];
    }

    // 合并集合
    void Union(int a, int b) {
        int pa = Find(a);
        int pb = Find(b);
        fa[pb] = pa;
    }

    int Insert(String s) {//将字符串 s 插入到字典树中
        int p = 1;
        for (int i = 0; i < s.length(); i++) {
            int ch = s.charAt(i) - 'a'; // 转换成数字
            if (trie[p][ch] == 0)
                trie[p][ch] = ++tot; // 记录下标
            p = trie[p][ch];
        }
        if (end[p]) // 颜色单词已存在
            return col[p];  //返回其颜色号
        else { // 否则创建单词
            end[p] = true;
            col[p] = ++color;
            return col[p];
        }
    }

    public String cal(String input) {
        Init();
        for (int i = 1; i < maxn; i++)
            fa[i] = i;


        String[] line = input.split("\n");

        for (int k = 0; k < line.length; k++) {
            String[] colors = line[0].split(" ");
            int i = Insert(colors[0]);
            int j = Insert(colors[1]); // 得到 a、b 颜色的编号
            degree[i]++;
            degree[j]++;// 记录 a、b 颜色出现的次数(总度数)
            Union(i, j);
        }
        int s = Find(1); // 若图为连通图，则 s 为所有结点的祖先
        int num = 0;  // 度数为奇数的结点个数
        for (int i = 1; i <= color; i++) {
            if (degree[i] % 2 == 1)
                num++;
            if (num > 2 || Find(i) != s) { // 存在多个祖先，图为森林，不连通
                output = "Impossible\n";
                return output;
            }
        }
        if (num == 0 || num == 2) // 没有奇度顶点或恰好两个奇度顶点
            output = "Possible\n";
        else
            output = "Impossible\n";
        return output;
    }
}
